home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
C/C++ Users Group Library 1996 July
/
C-C++ Users Group Library July 1996.iso
/
listings
/
v_11_12
/
allison
/
bitstr.cpp
< prev
next >
Wrap
C/C++ Source or Header
|
1993-10-10
|
9KB
|
448 lines
LISTING 5 - Bitstring Class Implementation
// bitstr.cpp
#include <assert.h>
#include <iostream.h>
#include <string.h>
#include "string.hpp"
#include "bitstr.h"
// Public Functions:
bitstring::bitstring(unsigned long val, size_t n)
{
assert(n < NPOS);
// val == 0 is easy...
if (val == 0)
{
init(n);
return;
}
// Find highest significant bit
unsigned long temp = val;
int high_bit = 0;
for (int i = 0; temp; ++i)
{
if (temp & 1)
high_bit = i;
temp >>= 1;
}
// Determine nbits_ and construct
nbits_ = high_bit + 1;
if (nbits_ < n)
nbits_ = n;
init(nbits_);
// Store bit pattern
for (i = 0; i < nbits_; ++i)
{
if (val & 1)
set_(i);
val >>= 1;
}
}
bitstring::bitstring(const string& s)
{
// Validate that s has only 0's and 1's
for (int i = 0; i < s.length(); ++i)
{
char c = s.get_at(i);
if (c != '0' && c != '1')
break;
}
assert(i == s.length());
from_string(s);
}
bitstring::bitstring(const bitstring& b)
{
init(b.nbits_);
memcpy(bits_,b.bits_,nblks_ * sizeof bits_[0]);
}
string bitstring::to_string() const
{
char *s = new char[nbits_+1];
for (int i = 0; i < nbits_; ++i)
s[i] = '0' + test_(i);
s[nbits_] = '\0';
string s2(s);
delete [] s;
return s2;
}
bitstring& bitstring::operator=(const bitstring& b)
{
if (this != &b)
{
delete [] bits_;
init(b.nbits_);
memcpy(bits_,b.bits_,nblks_ * sizeof bits_[0]);
}
return *this;
}
int bitstring::operator==(const bitstring& b) const
{
return (nbits_ == b.nbits_) &&
!memcmp(bits_,b.bits_,nblks_ * sizeof bits_[0]);
}
bitstring& bitstring::set()
{
memset(bits_,~0u,nblks_ * sizeof bits_[0]);
cleanup();
return *this;
}
bitstring& bitstring::set(size_t pos, int val)
{
assert(pos <= nbits_);
if (pos == nbits_)
length(nbits_ + 1); // Append
set_(pos,val);
return *this;
}
bitstring& bitstring::reset(size_t pos)
{
assert(pos <= nbits_);
if (pos == nbits_)
length(nbits_ + 1); // Append
reset_(pos);
return *this;
}
bitstring& bitstring::reset()
{
memset(bits_,0,nblks_ * sizeof bits_[0]);
return *this;
}
bitstring& bitstring::toggle()
{
size_t nw = nblks_;
while (nw--)
bits_[nw] = ~bits_[nw];
cleanup();
return *this;
}
int bitstring::any() const
{
for (int i = 0; i < nblks_; ++i)
if (bits_[i])
return 1;
return 0;
}
size_t bitstring::count() const
{
size_t sum = 0;
for (int i = 0; i < nbits_; ++i)
if (test_(i))
++sum;
return sum;
}
bitstring& bitstring::operator&=(const bitstring& b)
{
bitstring rhs(b);
equalize(rhs);
for (int i = 0; i < nblks_; ++i)
bits_[i] &= rhs.bits_[i];
return *this;
}
bitstring& bitstring::operator|=(const bitstring& b)
{
bitstring rhs(b);
equalize(rhs);
for (int i = 0; i < nblks_; ++i)
bits_[i] |= rhs.bits_[i];
cleanup();
return *this;
}
bitstring& bitstring::operator^=(const bitstring& b)
{
bitstring rhs(b);
equalize(rhs);
for (int i = 0; i < nblks_; ++i)
bits_[i] ^= rhs.bits_[i];
cleanup();
return *this;
}
bitstring& bitstring::operator>>=(size_t n)
{
if (n >= nbits_)
reset();
else
{
for (int i = nbits_ - 1; i >= n; --i)
(void) set_(i,test_(i-n));
for (i = 0; i < n; ++i)
reset_(i);
}
return *this;
}
bitstring& bitstring::operator<<=(size_t n)
{
if (n >= nbits_)
reset();
else
{
for (int i = 0; i < nbits_ - n; ++i)
(void) set_(i,test_(i+n));
for (i = nbits_ - n; i < nbits_; ++i)
reset_(i);
}
return *this;
}
bitstring& bitstring::operator+=(const bitstring& b)
{
assert(nbits_ + b.nbits_ < NPOS);
int oldlen = nbits_;
length(nbits_ + b.nbits_);
for (int i = 0; i < b.nbits_; ++i)
(void) set_(oldlen+i,b.test_(i));
return *this;
}
bitstring& bitstring::insert(size_t pos, const bitstring& b)
{
assert(pos <= nbits_);
size_t oldlen = nbits_;
size_t newlen = nbits_ + b.nbits_;
// Grow to accommodate insertion
length(newlen);
// Move tail to right
for (int i = 0; i < oldlen - pos; ++i)
set_(newlen-i-1,test_(oldlen-i-1));
// Replicate b in between
for (i = 0; i < b.nbits_; ++i)
set_(pos+i,b.test_(i));
return *this;
}
bitstring& bitstring::remove(size_t pos, size_t n)
{
assert(pos < nbits_);
if (n > nbits_ - pos)
n = nbits_ - pos;
// Slide tail down to cover gap
for (int i = 0; i < nbits_ - pos - n; ++i)
set_(pos+i,test_(pos+n+i));
// Shrink
length(nbits_ - n);
return *this;
}
bitstring& bitstring::replace(size_t pos, size_t n, const
bitstring& b)
{
assert(pos <= nbits_);
if (n > nbits_ - pos)
n = nbits_ - pos;
size_t oldlen = nbits_;
size_t newlen = oldlen - n + b.nbits_;
int diff = newlen - oldlen;
// Adjust length and move tail as needed
if (diff > 0)
{
// Grow
length(newlen);
for (int i = oldlen - 1; i >= pos + n; --i)
(void) set_(i+diff,test_(i));
}
else if (diff < 0)
{
// Shrink
for (int i = pos + n; i < oldlen; ++i)
(void) set_(i+diff,test_(i));
length(newlen);
}
// Copy b into place
for (int i = 0; i < b.nbits_; ++i)
(void) set_(pos+i,b.test_(i));
return *this;
}
size_t bitstring::find(int val, size_t pos) const
{
assert(pos < nbits_);
for (size_t i = pos; i < nbits_; ++i)
{
int t = test_(i);
if (val && t || !val && !t)
return i;
}
return NPOS;
}
size_t bitstring::rfind(int val, size_t pos) const
{
assert(pos < nbits_);
for (int i = pos; i >= 0; --i)
{
int t = test_(i);
if (val && t || !val && !t)
return i;
}
return NPOS;
}
bitstring bitstring::substr(size_t pos, size_t n) const
{
assert(pos <= nbits_);
if (n > nbits_ - pos)
n = nbits_ - pos;
bitstring b(0,n);
for (int i = 0; i < n; ++i)
b.set_(i,test_(pos + i));
return b;
}
size_t bitstring::length(size_t n, int val)
{
size_t oldlen = nbits_;
size_t nw1 = nblks_;
size_t nw2 = nblks(n);
// Alter the size of a bitstring
if (nw1 != nw2)
{
Block *newbits = new Block[nw2];
for (int i = 0; i < nw1 && i < nw2; ++i)
newbits[i] = bits_[i];
delete [] bits_;
bits_ = newbits;
for (i = nw1; i < nw2; ++i)
bits_[i] = val ? ~Block(0) : Block(0);
nblks_ = nw2;
}
nbits_ = n;
make_clean_mask();
cleanup();
return oldlen;
}
size_t bitstring::trim()
{
for (int i = nbits_ - 1; i >= 0; --i)
if (test_(i))
break;
size_t newlen = i + 1;
length(newlen);
return newlen;
}
ostream& operator<<(ostream& os, const bitstring& b)
{
os << b.to_string();
return os;
}
istream& operator>>(istream& is, bitstring& b)
{
const size_t N = 256;
char *buf = new char[N];
char c;
// Consume bit characters
is >> ws;
for (int i = 0; i < N && is.get(c); ++i)
{
if (c == '0' || c == '1')
buf[i] = c;
else
{
is.putback(c);
break;
}
}
buf[i] = '\0';
if (i == 0)
is.clear(ios::failbit);
else
{
delete [] b.bits_;
b.from_string(string(buf));
}
delete buf;
return is;
}
// Private Functions:
int bitstring::set_(size_t n, int val)
{
if (val)
set_(n);
else
reset_(n);
return !!val;
}
void bitstring::from_string(const string& s)
{
// Assumes string contains only 0's and 1's
init(s.length());
for (int i = 0; i < s.length(); ++i)
if (s.get_at(i) == '1')
set_(i);
}
void bitstring::init(size_t n)
{
nbits_ = n;
nblks_ = nblks(n);
if